package com.ayuer.chapter05;

/**
 * 基于数组二叉堆实现，小顶堆
 */
@SuppressWarnings("all")
public class MinHeap {

    int[] array;
    int size;

    public MinHeap(int[] arr) {
        this.size = arr.length;
        this.array = arr;
        this.heapify();
    }

    public MinHeap(int capacity) {
        this.size = 0;
        this.array = new int[capacity];
    }

    //floyd建堆算法，找到最后一个非叶子节点，就是size / 2 -1
    private void heapify() {
        //size / 2 - 1是最后一个非叶子节点
        //从索引0开始存储，节点i的父节点存在(i-1)/2，i>0时
        for (int i = size / 2 - 1; i >= 0; i--) {
            down2(i);
        }
    }

    /**
     * 威廉姆斯建堆算法，更优秀的建堆算法还有Floyd的算法
     * 1.加入新元素。加入到数组的末尾
     * 2.不断比较上浮比较新加元素的父元素的优先级
     *      如果父节点优先级低，则向下潜，找到下一个parent
     *      直到父节点优先级更高，或者child == 0
     * @param e
     * @return
     */
    public boolean offer(int offered) {
        if (isFull()) {
            return false;
        }
        int childIndex = size;
        int parentIndex = (childIndex - 1) / 2;
        while (childIndex > 0 && offered < array[parentIndex]) {
            //上浮
            array[childIndex] = array[parentIndex];
            childIndex = parentIndex;
            parentIndex = (childIndex - 1) / 2;
        }
        array[childIndex] = offered;
        size++;
        return true;
    }

    //下潜
    public void down(int parent) {
        int left = parent * 2 + 1;
        int right = left + 1;
        int min = parent;
        if (left < size && array[parent] > array[left]) {
            min = left;
        }

        if (right < size && array[parent] > array[right]) {
            min = right;
        }

        if (min != parent) {
            //交换
            swap(min, parent);
            //下潜
            down(min);
        }
    }

    /**
     * 1.从堆顶开始，与最后一个元素进行交换，移除最后一个元素
     * 2.调整堆结构，下潜
     *      从堆顶开始，将父元素与两个孩子的较大的元素进行交换
     *      直到父元素大于两个孩子元素，或者没有孩子为止
     * @return
     */
    public void down2(int parentIndex) {
        //从索引0开始存储，节点i的父节点存在(i-1)/2，i>0时
        //节点i的左子节点为2i+1，右节点为2i+2
        int leftIndex;
        int rightIndex;
        int min = parentIndex;
        while (true) {
            leftIndex = 2 * min + 1;
            rightIndex = 2 * min + 2;
            if (leftIndex < size && array[min] > array[leftIndex]) {
                min = leftIndex;
            }
            if (rightIndex < size && array[min] > array[rightIndex]) {
                min = rightIndex;
            }
            if (min != parentIndex) {
                //交换
                swap(min, parentIndex);
                parentIndex = min;
                continue;
            } else {
                break;
            }
        }
    }

    public void swap(int i, int j) {
        //交换
        int temp = array[i];//big
        array[i] = array[j];
        array[j] = temp;
    }

    //替换堆顶元素
    public void replace(int ele) {
        array[0] = ele;
        down2(0);
    }

    public int poll() {
        int head = array[0];
        //最后的节点上移
        array[0] = array[size - 1];
        array[size--] = 0;

        int parentIndex = 0;
//        down2(parentIndex);
        down2(parentIndex);
        return head;
    }

    public int poll(int index) {
        int deleted = array[index];
        array[index] = array[size - 1];
        array[size--] = 0;
        down2(index);
        return deleted;
    }

    public int peek() {
        return array[0];
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public boolean isFull() {
        return array.length == size;
    }
}
